def binary_search(sorted_array, val) -> bool:
    end=len(sorted_array)
    if end==0:
        return False
    mid=end//2

    if sorted_array[mid] == val:
        return True
    elif sorted_array[mid] > val:
        return binary_search(sorted_array[:mid],val)
    else:
        return binary_search(sorted_array[mid+1:],val)

def binary_search_recursive(sorted_array, beg, end, val)  ->int:
    if beg >= end:
        return -1
    mid = int((beg + end) / 2)  # beg + (end-beg)/2
    if sorted_array[mid] == val:
        return mid
    elif sorted_array[mid] > val:
        return binary_search_recursive(sorted_array, beg, mid, val)    # 注意我依然假设 beg, end 区间是左闭右开的
    else:
        return binary_search_recursive(sorted_array, mid+1, end, val)



nums= [17, 20, 26, 31, 44, 54, 55, 77, 93]
ans=binary_search_recursive(nums,0,len(nums),77)

print(ans)
binary_search(nums,77)